package com.changhong;

/**
 * Created by Administrator on 2018/12/17
 */
public class Sort001 {

    public static void main(String[] args) {
        Sort001 sort001 = new Sort001();
        sort001.data = SortTools.genData(10);
        sort001.data = new int[] {1 , 2, 2, 5,5,4,5};
        SortTools.print(sort001.data);
        sort001.sortQuick();
        SortTools.print(sort001.data);
    }

    int[] data;

    void sortQuick() {
        sortQuick(0, data.length - 1);
    }

    void sortQuick(int left, int right) {
        if (left >= right) {
            return;
        }
        int lt = left;
        int gt = right + 1;
        int value = data[left];
        for (int index = left; index < gt && index <= right; ) {
            if (data[index] < value) {
                lt++;
                swap(lt, index);
                index++;
            } else if (data[index] > value) {
                gt--;
                swap(index, gt);
            } else {
                index++;
            }
        }
        swap(left, lt);
        lt--;

        sortQuick(left, lt);
        sortQuick(gt, right);
    }

    void sortHeap() {
        for (int i = data.length / 2 - 1; i >= 0 ; i--) {
            adjustHeap(i, data.length);
        }
        SortTools.print(data);

        for (int i = 0; i < data.length; i++) {
            swap(0, data.length - 1 - i);
            adjustHeap(0, data.length - 1 -i);
        }
    }

    void adjustHeap(int root, int length) {
        while (root <= length / 2 - 1) {
            int left = 2 * root;
            int max = left;
            int right = left + 1;
            if (right <= length -1) {
                if (data[left] < data[right]) {
                    max = right;
                }
            }

            if (data[root] < data[max]) {
                swap(root, max);
                root = max;
            } else {
                break;
            }
        }
    }

    void sortInsert() {
        for (int i = 0; i < data.length; i++) {
            for (int j = i; j > 0; j--) {
                if (data[j - 1] > data[j]) {
                    swap(j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    void sortBubble() {
        for (int i = data.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[j + 1]) {
                    swap(j, j + 1);
                }
            }
        }
    }

    void sortMerge() {
        sortMerge(0, data.length - 1);
    }

    void sortMerge(int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        sortMerge(left, mid);
        sortMerge(mid + 1, right);
        merge(left, mid, right);
    }

    void merge(int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int indexLeft = left;
        int indexRight = mid + 1;
        int indexTemp = 0;
        while (indexLeft <= mid && indexRight <= right) {
            if (data[indexLeft] < data[indexRight]) {
                temp[indexTemp++] = data[indexLeft++];
            } else {
                temp[indexTemp++] = data[indexRight++];
            }
        }

        while (indexLeft <= mid) {
            temp[indexTemp++] = data[indexLeft++];
        }

        while (indexRight <= right) {
            temp[indexTemp++] = data[indexRight++];
        }

        indexTemp = 0;
        for (int i = left; i <= right; i++) {
            data[i] = temp[indexTemp++];
        }
    }

    void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
